package com.leetcode.array_matrix;

/**
 * @author Dennis Li
 * @date 2020/10/26 11:44
 */
public class CorpFlightBookings_1109 {

    // 暴力解法 -- 1043ms
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] ans = new int[n];
        for (int[] booking : bookings) {
            int start = booking[0] - 1, end = booking[1] - 1, num = booking[2];
            for (int i = start; i <= end; i++) {
                ans[i] += num;
            }
        }
        return ans;
    }

    // 差分数组 -- 3ms !!!!
    // 用于对一段区间进行增加或减少
    // diff[i] = nums[i] - nums[i - 1]
    // 对[i, j] 进行整体+1， 那么只需要对diff[i] + 1再对 diff[j + 1] - 1即可，i ~ j之间的大小关系维持原样
    // 而对最后的数组结果而言，只需要进行累加，即可求得原来的数组值
    public int[] corpFlightBookings2(int[][] bookings, int n) {
        int[] diff = new int[n], res = new int[n];
        for (int[] booking : bookings) {
            int i = booking[0] - 1, j = booking[1] - 1, num = booking[2];
            diff[i] += num;
            if (j < n - 1) diff[j + 1] -= num;
        }
        res[0] = diff[0];
        for (int i = 1; i < n; i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }

}
